package practice;

import java.util.Arrays;

/**
 * 二叉堆
 */
public class HeapDemo {

    private static abstract class AbstractHeap {
        /**
         * 存储结构
         */
        private final int[] arr;
        /**
         * 当前的索引
         */
        private int index = 0;
        /**
         * 堆的大小
         */
        private final int length;

        public AbstractHeap(int length) {
            this.length = length;
            this.arr = new int[length];
        }

        protected AbstractHeap(int[] arr) {
            this.arr = arr;
            this.length = arr.length;
            this.index = arr.length;
        }

        /**
         * 比较两个元素
         * @param a1
         * @param a2
         * @return 如果a1小于a2返回true，否则返回false
         */
        protected abstract boolean compare(int a1, int a2);

        /**
         * 添加一个元素
         * @param n
         */
        public void add(int n) {
            if(index + 1 >= length)
                throw new RuntimeException("heap full");
            arr[index] = n;
            floatingUp(index);
            index ++;
        }

        /**
         * 删除一个元素
         * @return
         */
        public int remove() {
            int t = arr[0];
            arr[0] = arr[-- index];
            sink(0);
            return t;
        }

        /**
         * 下沉
         */
        protected void sink(int i) {
            if(i > length || i < 0)
                throw new RuntimeException("index > length");
            int limit = index - 1;
            if(i == limit)
                return;
            int leftIndex, rightIndex, minIndex, t = arr[i];
            for(;;) {
                if((leftIndex = i * 2 + 1) > limit)
                    break;
                if((rightIndex = leftIndex + 1) > limit) {
                    minIndex = leftIndex;
                } else {
                    minIndex = compare(arr[leftIndex], arr[rightIndex]) ? leftIndex : rightIndex;
                }
                if(!compare(t, arr[minIndex])) {
                    arr[i] = arr[minIndex];
                    i = minIndex;
                } else
                    break;
            }
            arr[i] = t;
        }

        /**
         * 上浮
         */
        protected void floatingUp(int i) {
            if(i > length || i < 0)
                throw new RuntimeException("index > length");
            if(i == 0)
                return;
            int t = arr[i];
            int pIndex;
            while(i > 0 && compare(t, arr[(pIndex = (i - 1) / 2)])) {
                arr[i] = arr[pIndex];
                i = pIndex;
            }
            arr[i] = t;
        }

        @Override
        public String toString() {
            return Arrays.toString(arr);
        }
    }

    /**
     * 最小堆
     */
    private static class MinHeap extends AbstractHeap {
        public MinHeap(int length) {
            super(length);
        }

        private MinHeap(int[] arr) {
            super(arr);
        }

        @Override
        protected boolean compare(int a1, int a2) {
            return a1 < a2;
        }

        /**
         * 构建堆
         */
        public static MinHeap build(int... arr) {
            if(arr == null)
                return null;
            MinHeap minHeap = new MinHeap(arr);
            int i = (arr.length - 2) / 2;
            while(i >= 0) {
                minHeap.sink(i --);
            }
            return minHeap;
        }
    }

    /**
     * 最大堆
     */
    private static class MaxHeap extends AbstractHeap {

        public MaxHeap(int length) {
            super(length);
        }

        protected MaxHeap(int[] arr) {
            super(arr);
        }

        @Override
        protected boolean compare(int a1, int a2) {
            return a2 < a1;
        }

        /**
         * 构建堆
         */
        public static MaxHeap build(int... arr) {
            if(arr == null)
                return null;
            MaxHeap minHeap = new MaxHeap(arr);
            int i = (arr.length - 2) / 2;
            while(i >= 0) {
                minHeap.sink(i --);
            }
            return minHeap;
        }
    }

    public static void main(String[] args) {
        AbstractHeap heap1 = new MaxHeap(10);
        heap1.add(0);
        heap1.add(1);
        heap1.add(2);
        heap1.add(3);
        heap1.add(4);
        heap1.add(5);
        heap1.add(-1);
        System.out.println(heap1);
        int removed = heap1.remove();
        System.out.println("removed: " + removed);
        System.out.println(heap1);

        AbstractHeap heap2 = MaxHeap.build(7, 1, 3, 10, 5, 2, 8, 9, 6);
        System.out.println(heap2);
    }
}
